package com.shuang.stackAndQueue4;

import java.util.ArrayDeque;

public class RemoveDuplicates {

    public String removeDuplicates(String s) {

        //使用 Deque 作为堆栈 遍历字符串 往栈中存的时候 判断当栈顶元素与下一个字符串元素重复时 直接弹出栈顶元素
        //栈中剩下的元素就是去除相邻重复字符的字符串 弹出后组成字符串返回即可

        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            //去除重复相邻元素
            if (!deque.isEmpty() && ch == deque.peek()) {
                deque.pop();
            } else {
                //不是相邻重复加到栈中
                deque.push(ch);
            }
        }

        //循环结束 栈中元素为去除相邻字符的字符串 依次压出组成字符串
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str; //弹出与拼接字符串顺序时做了一个调整
        }
        return str;
    }
}
